The present invention relates to transmitting data over a network. In particular, the present invention relates to systems and methods for transmitting data using multiple description vector quantization.
Many ways are known for transmitting different types of data over a network. For example, FIG. 1 displays a block diagram of a system that can transmit audio or video data. In this configuration, source 101 provides some form of analog data. That data is then converted to a digital stream, or quantized, at analog-to-digital converter (ADC) 102. Once the data is quantized, it can be easily encoded by encoder 103, and transmitted to receiver 105 over network 104. Receiver 105 passes the data to decoder 106, which decodes the data, thereby substantially recreating the original data stream. If the data is audio, for example, decoder 106 typically will recreate the data with some level of accuracy so the data can be played and recognized in an acceptable fashion. This configuration is called a xe2x80x9csingle descriptionxe2x80x9d system because only a single stream of data is transmitted from the source to the receiver.
If, however, part of the data-stream transmission is disrupted during its transmission from the source to the receiver, acceptable reconstruction at the receiver may not be possible. To minimize disruptions during transmission, xe2x80x9cmultiple descriptionxe2x80x9d systems can be used. In a multiple-description scheme, an encoder generates multiple streams of data. Each data stream in the multiple streams of data can individually reproduce the original data in an acceptable form. If the decoder receives all the data streams, the original data can be reconstructed very accurately. On the other hand, if only one data stream is received, and reconstructed to X1nxe2x80x2, the reconstructed data, and hence the playback, will not be as high quality as the complete reconstruction, but will be acceptable, at least over a short time scale. In general, receiving all the data streams gives optimal reconstruction, but over short periods of time, if one data stream is missing, that missing data stream can be dropped from the reconstruction without serious diminution of the quality of the reconstructed data.
FIG. 2 is a block diagram of the components of a multiple-description system. In this system, source 201 again provides analog data, and this data is quantized at ADC 202. After quantization, the digital data is encoded for transmission at encoder 203. Encoder 203, in a multiple-description scheme, encodes the data into multiple streams for transmission. In FIG. 2, only two streams are shown for simplicity, and only two streams are discussed for simplicity; in principle, however, an arbitrary number of encoded streams can be created and used.
Once the two streams are encoded, they are independently transmitted over network 204 to receiver 205. Receiver 205 contains, in this example, three decoders, 205a, 205b and 205c. If both streams are received at decoder 205a, the two streams are recombined into an effective reconstruction of the data. If, however, only one of the streams arrives at receiver 205, decoder 205b or 205c can decode the data into an acceptable reconstruction of the original data. This reconstruction will typically be of lesser quality than if the two streams are received and combined at decoder 205a. In general, if parts of one transmitted stream are dropped, then those parts of the transmission will be recreated using the single stream that arrives at the receiver, and the rest of the transmission will be recreated using the two combined streams that are received at decoder 205a. A decoded single stream will then be played back to a viewer or listener, for example, at the appropriate time during playback, while the recombined double stream will played at all other times.
Known systems use a type of multiple-description coding called xe2x80x9clayerxe2x80x9d or xe2x80x9chierarchicalxe2x80x9d coding. In these schemes, an encoder generates two or more streams of bits of varying importance. For example, if two streams are generated, one stream is considered more important than the other stream. This scheme gives the network flexibility to drop bits if, for example, the network is congested. If the network is congested, the network can choose to drop the less-important bits. In this scheme, the network guarantees that it always is going to deliver the most important stream of bits. Thus, users are assured a certain basic quality in the reconstructed video or audio data. If a user, on the other hand, can receive more streams of data, the playback will be of higher quality.
Two general schemes exist for multiple-description coding. One scheme, called scalar quantization, quantizes the source data by assigning a single data number to each sample of the source data. This scalar quantization can be visualized with reference to FIG. 3. FIG. 3 is a representation of scalar quantization in which the horizontal axis represents charge, and the vertical axis represents discrete binary numbers that are assigned to a received charge. With scalar quantization, the input is a scalar, or one-dimensional, quantity. If input voltage is known to lie in a certain range, and only 8 bits are used for quantization, the voltage range is divided up by partitioning the input-voltage range into a series of sub-ranges, and a distinct binary number is assigned to each sub-range.
Another form of quantization, called vector quantization, quantizes the source data by applying a single data number to a fixed plurality of samples of the source data. With vector quantization, voltage input is generalized into multiple dimensions. Thus the charge input has indices, x=(xn, xn+1 . . . xn+m). x is a charge input that is sampled, for example, at multiple times. Thus, for example, xn might be a charge at time=n, and x+1 would be the charge at time=n+1.
Vector quantization can be visualized with reference to FIG. 4. FIG. 4 is a two-dimensional graph in which the vertical and horizontal axes each represent charge sampled in some way from analog data. Each two-dimensional area in the represented plane is assigned a unique data number, thereby encoding the vector represented by every point in the plane. Using the example above, the horizontal axis can represent speech data sampled at time xn, and the vertical axis can represent data sampled at time xn+1. Note that a two-dimensional plane is used merely for simplicity of representation. A quantized vector can contain an arbitrary number of sampled points.
An achievable rate region for the multiple description problem was first given by El Gamal and Cover in their article titled xe2x80x9cAchievable rates for multiple descriptions,xe2x80x9d IEEE Trans. Inform. Th., vol. IT-28, November 1982, and Ozarow has shown that this region coincides with the rate distortion region for a memoryless Gaussian source and the squared-error distortion. See L. Ozarow, xe2x80x9cOn a source coding problem with two channels and three receivers.xe2x80x9d The Bell Syst. Tech. J., vol. 59, December 1980. Both articles are incorporated herein by reference. The problem of multiple description quantizer design, including a formulation and solution of the underlying labeling problem in one dimension was presented in a paper by V. A. Vaishampayan, titled xe2x80x9cDesign of multiple description scalar quantizers,xe2x80x9d IEEE Trans. Inform. Theory, vol. 39, pp. 821-34, May 1993, incorporated herein by reference. An asymptotic performance analysis of this quantizer was presented in J. C. Battlo and V. A. Vaishampayan, xe2x80x9cMultiple-description transform codes with an application to packetized speech,xe2x80x9d in Proceedings of the 1994 IEEE International Symposium on Information Theory, Trondhaim, Norway, June 1994 incorporated herein by reference.
Lattice quantizers (for the single description problem) have been extensively studied. Zador, in his paper titled xe2x80x9cAsymptotic quantization error of continuous signals and the quantization dimension,xe2x80x9d IEEE Trans. Inform. Th., vol. IT-28, pp. 139-49, March 1982, incorporated herein by reference, used a random quantization argument to give upper and lower bounds on the performance of quantizers for a fixed dimension. Detailed descriptions of the Voronoi regions of specific lattices are given by Conway and Sloane in Sphere Packings, Lattices and Groups. New York: Springer-Verlag, 1988, incorporated herein by reference, and their second moments are evaluated. Fast quantizing algorithms for lattice quantizers are given in J. H. Conway and N. J. A. Sloane, xe2x80x9cFast quantizing and decoding algorithms for lattice quantizers and codes,xe2x80x9d IEEE Trans. Inform. Th., vol. 28, pp. 227-32, March 1982, incorporated herein by reference. Gersho, in xe2x80x9cAsymptotically optimal block quantization,xe2x80x9d IEEE Trans. Inform. Th., vol. IT-25, pp. 373-80, July 1979, incorporated herein by reference, conjectured that for rth power difference distortion measures, any optimal quantizer, in any dimension, has Voronoi regions that are congruent to some polytope.
For multiple-description, hierarchical coding, it does not matter whether the quantization is scalar or vector. What matters is simply that more than one data stream is produced, and each data stream is given a certain relative importance with respect to the other data streams. Many networks, however, cannot guarantee that the most important bits are going to reach their destination. For example, the Internet cannot make any such guarantee. In these cases, the layered approaches do not work very well, because if the most important bits in a data stream are lost, the data may not be reconstructable in a usable form. Thus, a need exists for a multiple-description scheme that does not rely on a hierarchy of data schemes, and so does not rely on a guarantee by the network to deliver the most important data stream.
To alleviate the problems inherent in known systems, the present invention introduces systems and methods for coding and transmitting data using multiple description lattice vector quantization with lattice codebooks. In one embodiment of the present invention, a source vector is quantized at a lattice vector quantizer. A labeling function is then applied to the quantized source vector, thereby creating at least a first data stream and a second data stream. The first and second data streams are then encoded and transmitted.
To apply the labeling function, in one embodiment of the present invention, the quantized source vector is associated with at least a first sublattice point associated with a first data code word and a second sublattice point associated with a second data code word. The first data code word is then transmitted in the first data stream, and the second data code word is transmitted in the second data stream.
At the receiving end of the transmission, if all data streams are received intact, they are recombined by a decoder, and prepared for playback. If one or more data stream, however, contains gaps when received, the remaining data stream or streams are combined and played back without those missing portions of the incomplete data stream.